The development and application of rule engines is one branch of Artificial Intelligence (A.I.), which is a very broad research area that focuses on “making computers think like people.” Broadly speaking, a rule engine is a set of one or more software modules running on a computing device (e.g., a server, a personal computer, etc.) that processes information by applying rules to data objects (e.g., facts). A rule is a logical construct for describing the operations, definitions, conditions, and/or constraints that apply to some predetermined data to achieve a goal. Various types of rule engines have been developed to evaluate and process rules. Conventionally, a compiler compiles a rulebase containing a network constructed according to a set of rules. Then a rule engine evaluates the compiled rulebase against data objects, such as facts. The network may include many different types of nodes, including, for example, object-type nodes, alpha nodes, left-input-adapter nodes, eval nodes, join nodes, not nodes, and terminal nodes, etc.
Typically, facts enter a network at the root node, from which they are propagated to any matching object-type nodes. From a object-type node, a data object is propagated to either an alpha node (if there is a literal constraint), a left-input-adapter node (if the data object is the left most object type for the rule), or a beta node (such as a join node). However, connections between the nodes in the network are synchronous and typically, only one fact is propagated through the network at a time.
However, use cases like event processing, where a huge volume of data is processed, but a relatively low volume of actions are taken as a result of the processing, stress the evaluation algorithm to the most, while keeping the actual rule and/or query activations low. To support such scenarios, conventional event processing products run specialized algorithms that treat each rule or query on the event stream and/or cloud individually, allowing high parallelization but limiting the ability of optimizations. These algorithms do not perform well or even do not allow for rules reasoning.
On the other hand, trying to use conventional rule engine algorithms, like RETE, to process events is not feasible, due to the synchronization requirements of such algorithms. Namely, in order to ensure reasoning integrity, the algorithm forces synchronized reasoning, although, the actual matching algorithm accepts some level of parallelism as described by Charles Forgy, Anoop Gupta, and Allen Newel in the paper “High-Speed Implementations of Rule-Based Systems.”
In this paper, they discuss the possible gains of Rete parallelization on three levels: matching, conflict resolution, and action steps. In particular, they describe a possible solution for rule parallelization as creating a network composed of multiple partitions, where each partition would include a single rule. Each rule could then be assigned a thread and be processed in parallel. As they note, this solution has a big drawback that is the loss of all the optimizations a Rete network could have, especially node sharing, that in their calculations increase processing cost by a factor of about 1.6.